package developer.算法.二叉树.反转二叉树;


import java.util.ArrayList;
import java.util.List;

/**
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 *
 * @author zhangyongkang
 * @since 2024/7/11 10:01
 */
public class Solution_other {

    /**
     * /**
     * * Definition for a binary tree node.
     * * public class TreeNode {
     * *     int val;
     * *     TreeNode left;
     * *     TreeNode right;
     * *     TreeNode() {}
     * *     TreeNode(int val) { this.val = val; }
     * *     TreeNode(int val, TreeNode left, TreeNode right) {
     * *         this.val = val;
     * *         this.left = left;
     * *         this.right = right;
     * *     }
     * * }
     */

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        /**
         * 作者：力扣官方题解
         * 链接：<a href="https://leetcode.cn/problems/invert-binary-tree/solutions/415160/fan-zhuan-er-cha-shu-by-leetcode-solution/">...</a>
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         *
         * @param root
         * @return
         */
        public static TreeNode invertTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            root.left = right;
            root.right = left;
            return root;
        }

        static class Solution4 {
            public TreeNode invertTree(TreeNode root) {
                if (root == null) {
                    return root;
                }

                TreeNode left = invertTree(root.left);
                TreeNode right = invertTree(root.right);
                root.left = right;
                root.right = left;
                return root;
            }
        }

        public static void main(String[] args) {
            TreeNode treeNode = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(7, new TreeNode(6), new TreeNode(9)));
            List<Integer> list = new ArrayList<>();
            LDR(treeNode, list);
            list.forEach(System.out::println);
            TreeNode treeNode1 = invertTree(treeNode);
            System.out.println("***************");
            List<Integer> list1 = new ArrayList<>();
            LDR(treeNode1, list1);
            list1.forEach(System.out::println);
        }

        public static void LDR(TreeNode root, List<Integer> list) {
            if (root == null) {
                return;
            }
            LDR(root.left, list);
            list.add(root.val);
            LDR(root.right, list);
        }
    }
}
